package com.fr.lintcode;

import java.util.Stack;

public class Q689 {

    /*
     * @param : the root of tree
     * @param : the target sum
     * @return: two numbers from tree which sum is n
     */
    public int[] twoSum(TreeNode root, int n) {
        // write your code here
        if (root == null) {
            return null;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.add(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (n != node.val * 2) {
                boolean find = search(root, n - node.val);
                if (find) {
                    return new int[] {node.val, n - node.val};
                }
            }
            if (node.left != null) {
                stack.add(node.left);

            }
            if (node.right != null) {
                stack.add(node.right);
            }
        }
        return null;
    }

    private boolean search(TreeNode root, int target) {
        TreeNode node = root;
        while (node != null) {
            if (node.val > target) {
                node = node.left;
            } else if (node.val == target) {
                return true;
            } else {
                node = node.right;
            }
        }
        return false;
    }
}
